package exercises.leetcode;

/**
 * <a href="https://leetcode-cn.com/problems/valid-parentheses/">
 * 20. 有效的括号</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "()"
 * 输出：true
 * <p>
 * 示例 2：
 * <p>
 * 输入：s = "()[]{}"
 * 输出：true
 * <p>
 * 示例 3：
 * <p>
 * 输入：s = "(]"
 * 输出：false
 * <p>
 * 示例 4：
 * <p>
 * 输入：s = "([)]"
 * 输出：false
 * <p>
 * 示例 5：
 * <p>
 * 输入：s = "{[]}"
 * 输出：true
 * <p>
 * 提示：
 * <li>1 <= s.length <= 104</li>
 * <li>s 仅由括号 '()[]{}' 组成</li>
 *
 * @author or2
 * @date 2021年09月27日 时间: 9:42
 */
public class No20 {
    public boolean isValid(String s) {
        /*辅助 - 栈*/
        int length = s.length();
        /*多一块空间防止溢出*/
        byte[] stack = new byte[length + 1];
        short sp = (short) (length - 1);

        char[] charArray = s.toCharArray();
        for (int i = 0; i < length; i++) {
            switch (charArray[i]) {
                case '(':
                    stack[sp--] = 1;
                    break;
                case '{':
                    stack[sp--] = 2;
                    break;
                case '[':
                    stack[sp--] = 3;
                    break;
                case ')':
                    if (stack[++sp] != 1)
                        return false;
                    break;
                case '}':
                    if (stack[++sp] != 2)
                        return false;
                    break;
                case ']':
                    if (stack[++sp] != 3)
                        return false;
                    break;
                default:
                    break;
            }
        }

        return sp == s.length() - 1;
    }


    public boolean isValidBitVersion(String s) {
        /*辅助 - 栈*/
        int length = Math.max((s.length() + 1) / 16, 1) + 1;
        int[] stack = new int[length];
        short spOuter = (short) (length - 1);
        /*多一块空间防止溢出*/
        byte spInner = 1;

        char[] charArray = s.toCharArray();
        for (int i = 0, sLen = s.length(), weight; i < sLen; i++) {
            weight = 0;
            switch (charArray[i]) {
                case '(':
                    weight++;
                case '{':
                    weight++;
                case '[':
                    weight++;
                    /*入栈*/
                    stack[spOuter] &= -1 - (3 << 2 * spInner);
                    stack[spOuter] |= weight << 2 * spInner;
                    spInner++;
                    if (spInner == 16) {
                        spOuter--;
                        spInner = 0;
                    }
                    break;
                case ')':
                    weight++;
                case '}':
                    weight++;
                case ']':
                    weight++;
                    /*出栈, 判断是否满足条件*/
                    spInner--;
                    if (spInner == -1) {
                        spOuter++;
                        spInner = 15;
                    }
                    if ((weight << 2 * spInner) != (stack[spOuter] & 3 << 2 * spInner))
                        return false;
            }
        }

        return spOuter == length - 1 && spInner == 1;
    }

//———————————————— 极致空间压缩, 用好int的每一位 ——————————————————————————————————
    public boolean isValidBitVersionNoCharArray(String s) {
        /*辅助 - 栈*/
        int length = Math.max((s.length() + 1) / 16, 1) + 1;
        int[] stack = new int[length];
        short spOuter = (short) (length - 1);
        /*多一块空间防止溢出*/
        byte spInner = 1;

        for (int i = 0, sLen = s.length(), weight; i < sLen; i++) {
            weight = 0;
            switch (s.charAt(i)) {
                case '(':
                    weight++;
                case '{':
                    weight++;
                case '[':
                    weight++;
                    /*入栈*/
                    stack[spOuter] &= -1 - (3 << 2 * spInner);
                    stack[spOuter] |= weight << 2 * spInner;
                    spInner++;
                    if (spInner == 16) {
                        spOuter--;
                        spInner = 0;
                    }
                    break;
                case ')':
                    weight++;
                case '}':
                    weight++;
                case ']':
                    weight++;
                    /*出栈, 判断是否满足条件*/
                    spInner--;
                    if (spInner == -1) {
                        spOuter++;
                        spInner = 15;
                    }
                    if ((weight << 2 * spInner) != (stack[spOuter] & 3 << 2 * spInner))
                        return false;
            }
        }

        return spOuter == length - 1 && spInner == 1;
    }
}
